class Solution {
public:
    void getNext(vector<int>& next,string& s){
        int j = 0;
        for(int i = 1;i < s.size();i++){
            while(j > 0 && s[j] != s[i]){
                j = next[j - 1];
            }
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
    }
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        vector<vector<int> > ret(smalls.size());
    
        for(int i = 0;i < smalls.size();i++){
            vector<int> next(smalls[i].size());
            if(smalls[i].size() == 0) continue;
            getNext(next,smalls[i]);
            
            for(int k = 0,j = 0;k < big.size();k++){
                while(j > 0 && big[k] != smalls[i][j]){
                    j = next[j - 1];
                }
                if(big[k] == smalls[i][j]){
                    j++;
                }
                if(j == smalls[i].size()){
                    ret[i].push_back(k - j + 1);
                }
            }
        }
        return ret;
    }
};
